package com.ocean.divideandconquer.easy;

import com.ocean.TreeNode;

/**
 * https://leetcode.cn/problems/minimum-height-tree-lcci/
 * <p>
 * <p>
 * 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
 * <p>
 * 示例:
 * 给定有序数组: [-10,-3,0,5,9],
 * <p>
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * <p>
 *          0
 *         / \
 *       -3   9
 *       /   /
 *     -10  5
 */
public class MinimumHeightTreeLcci {


    public static void main(String[] args) {
        MinimumHeightTreeLcci treeLcci = new MinimumHeightTreeLcci();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode treeNode = treeLcci.sortedArrayToBST(nums);

    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        int value = nums[mid];
        TreeNode root = new TreeNode(value);
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }
}
